T1 空泣

原题 P11663，是小 X 推荐的，使用了小 S 帮忙搞的官方数据。

比较容易，也没卡 $\mathcal O(n\log n)$ 做法，难度不超过绿。

另外子任务 $3,4$ 没想到简便做法，有的话欢迎分享。

Sol.1

枚举答案，再枚举起始位置，每次 $\mathcal O(n)$ 扫一遍判合法。复杂度 $\mathcal O(n^2r)$，其中 $r$ 为答案，期望得分 $10$。

Sol.2

$x$ 合法必有 $x+1$ 也合法，于是答案可二分，同样枚举起始位置判断即可。复杂度 $\mathcal O(n^2\log V)$，期望得分 $30$。

Sol.3

枚举起始位置后快速算答案，以从 $1$ 开始为例，答案为 $\max_{i=1}^n a_i-s_{i-1}$，其中 $s$ 为 $b$ 的前缀和。对所有起点的答案求最值即可，复杂度 $\mathcal O(n^2)$，期望得分 $30$。

Sol.4

将 $a,b$ 重复一遍实现断环为链，在长为 $2n$ 的数组上对 $b$ 做前缀和得到 $s$。之后对 $p\in[1,n]$ 分别求区间 $[p,p+n-1]$ 的答案，即 $\max_{i=p}^{p+n-1} a_i-(s_{i-1}-s_{p-1})$，求 $a_i-s_{i-1}$ 的区间最小值即可。区间左右端点均递增，可单调队列 $\mathcal O(n)$ 解决，期望得分 $100$，当然也可以前后缀分别求。另外 ST 表或线段树的 $\mathcal O(n\log n)$，以及二分的 $\mathcal O(n\log V)$ 都能过。

T2 诗空茫

小 X 供题的加强，他给的是 $n\le 5000,m=10^7+7$，也就是本题的 $80$。

$80$ 大概是绿题难度，后面 $20$ 非常难推，推导难度可能有紫到黑，个人只会已知结论倒过来证明，如果会打表 + 注意力够强应该也能做出来。

不存在长为 $3$ 的上升子序列即最长上升子序列长度不超过 $2$，用 $n!$ 减去这样的排列数量即为答案。

Sol.1

暴力枚举全排列或状压 DP，复杂度 $\mathcal O(n!\text{poly}(n))$ 或 $\mathcal O(2^n\text{poly}(n))$，期望得分 $[5,15]$。

Sol.2

考虑最长上升子序列的求解过程，即从左往右扫，实时维护当前长为 $i$ 的上升子序列结尾最小值 $g_i$。由于长度不超过 $2$，且显然 $g_1=1$，状态为 $f_{i,x}$ 表示长为 $i$ 的排列中 $g_2=x$ 的数量，边界为 $f_{2,2}=1$。

状态中 $x$ 即前 $i$ 个数中当前 $g_2$ 的相对排名，于是枚举 $p_{i+1}$ 在前 $(i+1)$ 个数中的相对排名即可转移。注意还需考虑从降序排列转移来的情况，最后也要把降序排列减去。复杂度 $\mathcal O(n^3)$，期望得分 $40$。

Sol.3

另一种思路是从小往大填，此时新加的值最大，因此不能放在当前长为 $2$ 的上升子序列（顺序对）之后，于是状态内需记录最靠前的顺序对结尾。设 $f_{i,j}$ 表示填了前 $i$ 小值后最靠前的顺序对结尾为 $j$ 的排列数量，边界为 $f_{2,2}=1$，可枚举 $(i+1)$ 的相对位置转移，细节同上。复杂度 $\mathcal O(n^3)$，期望得分 $40$。

感性理解可以发现上面两种做法基本相同，其实写出来一模一样，本质是在 $(i,p_i)$ 的二维平面内扫描一维，并记录另一维的信息以便转移。

$m=998244353$ 是给 $\mathcal O(n^3)$ 做法打表的，期望得分 $50$。这也是为什么只有 $n$ 的计数题要输入模数。

Sol.4

上面的 $\mathcal O(n^3)$ 做法非常容易后缀和优化，于是就 $\mathcal O(n^2)$ 了，期望得分 $80$。

Sol.5

给出结论：长为 $n$ 且最长上升子序列长度不超过 $2$ 的排列数量为卡特兰数第 $n$ 项。

证明考虑构造双射，将 $n$ 个点 $(i,p_i)$ 画到平面上，找到 $p_i$ 后缀最大值位置集合。以这些位置为拐点，画出从 $(n,0)$ 到 $(0,n)$ 的折线。由于长为 $i$ 的后缀最大值不低于 $i$，折线除端点外均在直线 $x+y=n$ 上方。于是从后往前，每个前缀中向上次数不低于向左次数，作为两种括号即为合法括号序列，合法折线数量即卡特兰数。

显然任意排列可映射到唯一合法折线，下面证明任意合法折线可映射到唯一合法（最长上升子序列长度不超过 $2$ ）排列。对于合法折线，可通过拐点还原出所有后缀最大值及位置。要构成合法排列，剩余值必须按降序依次填入空位，否则存在非后缀最大值位置 $i\lt j,p_i\lt p_j$，此时找到某个后缀最大值位置 $k\gt j$，长为 $3$ 的上升子序列 $i,j,k$ 会使排列非法。于是结论得证，合法排列与合法折线形成双射，两者数量相等，均为卡特兰数。

于是求卡特兰数第 $n$ 项 $\frac {2n\choose n}{n+1}$，在 $m$ 为质数时可通过阶乘及逆元求，复杂度 $\mathcal O(n)$。期望得分 $20$，拼上 Sol.4 期望得分 $90$。

Sol.6

$m$ 为合数时有的数不存在乘法逆元，无法实现除法。将式子拆组合数约分得到 $\frac{\prod_{i=n+2}^{2n}i}{\prod_{i=1}^ni}$，可求出该值中每个质因子的次数，最后快速幂求出答案。线性筛出 $2n$ 内所有质数及每个数的最小质因子，之后依次分解质因数加入，用桶维护当前次数即可。复杂度为分解质因数的 $\mathcal O(n\log n)$，期望得分 $100$。最后的快速幂其实是 $\mathcal O(n)$ 的，因为质数只有 $\mathcal O(\frac {n}{\log n})$ 个。

T3 血路

SDSC2025 D3T3 By do_while_true，原题。

数据自造，强度未知，但已经对着小 S 的错解尽可能卡了。

最优解中所有区间必然首尾相接，否则可调整消掉中间的空位。

另外可先找到所有区间的交点 $x$，并通过整体平移将交点变为 $0$，方便之后讨论。这样就变成原题了。

Sol.1

根据上述结论可以写一些暴力，期望得分 $[5,30]$。

Sol.2

观察最优解结构，设完全在 $0$ 左侧的区间有 $x$ 个，完全在 $0$ 右侧的区间有 $y$ 个。只要 $x\ne y$，就能将解整体向 $x,y$ 中较小的一侧平移，这样这些区间贡献严格减少，包含 $0$ 的区间只可能贡献 $1,-1$，总体代价必然不增。

若 $n$ 为偶数，根据上述调整最优解必然存在一个区间端点为 $0$，且 $0$ 将所有区间分成数量相同的两部分，这可以 DP 解决。令左右两侧区间集合从远到近分别为 $p,q$，零下标下答案为 $\sum_{i=0}^{\left|p\right|-1} (r_{p_i}+\sum_{j=i+1}^{\left|p\right|-1} len_{p_j})+\sum_{i=0}^{\left|q\right|-1}(-l_{q_i}+\sum_{j=i+1}^{\left|q\right|-1}len_{q_j})$，其中 $len_i=r_i-l_i$，含义即所有区间需要移动的次数和。

将 $len$ 项拆贡献避免对 $j$ 的枚举，可得 $\sum_{i=0}^{\left|p\right|-1} (r_{p_i}+ilen_{p_i})+\sum_{i=0}^{\left|q\right|-1}(-l_{q_i}+ilen_{q_i})$，最小化时显然小的 $i$ 应对应大的 $len$，即 $p,q$ 分别按 $len$ 降序排序最优。于是初始对所有区间按 $len$ 排序，之后 DP 设 $f_{i,j}$ 表示前 $i$ 个区间中 $j$ 个在 $0$ 左侧的最小贡献和，即可 $\mathcal O(n^2)$ 解决偶数情况，期望得分 $50$。

Sol.3

对于 $n$ 为奇数的情况，最终两侧区间数量必然相等。此时在中间区间包含 $0$ 的前提下左右平移时，两侧区间贡献不变，因此中间区间位于初始位置最优。令中间区间为 $t$，$p,q$ 含义同上，答案为$\sum_{i=0}^{\left|p\right|-1} (r_{p_i}+\sum_{j=i+1}^{\left|p\right|-1} len_{p_j})+\sum_{i=0}^{\left|q\right|-1}(-l_{q_i}+\sum_{j=i+1}^{\left|q\right|-1}len_{q_j})-\left|p\right|l_t+\left|q\right|r_t$，即两侧区间初始要移到 $t$ 两侧。枚举中间区间 $t$ 后可以同样 DP，总复杂度 $\mathcal O(n^3)$，期望得分 $35$，拼上 Sol.2 期望得分 $85$。

Sol.4

事实上由于 $\left|p\right|=\left|q\right|=\frac{n-1}2$，式子最后两项必为 $\frac{n-1}2len_t$。于是不需要枚举中间区间，直接设 $f_{i,j,0/1}$ 表示前 $i$ 个区间中 $j$ 个在 $0$ 左侧，是否已有中间区间的最小贡献和，过程中确定即可做到 $\mathcal O(n^2)$。另外部分转移与偶数情况相同，偶数时不选中间区间即可，可以写在一起。期望得分 $100$。

T4 欲泪海

SDSC2025 D1T4 By yixiuge777，原题 CF1540D，其实也没有特别难。

另外特殊性质 B 没想到简便做法，有的话欢迎分享。

Sol.1

每次询问枚举全排列，复杂度 $\mathcal O(qn!\text{poly}(n))$，期望得分 $5$。

Sol.2

注意到 $b_i$ 确定了 $p_i$ 在前 $i$ 个数中的相对排名，于是从左往右扫，维护当前前缀内所有数的大小关系，每次将 $i$ 插入到第 $(b_i+1) $ 大的位置；也可以从右往左扫，每次将 $p_i$ 确定为当前未使用过的第 $(b_i+1)$ 大值。这样可以求出整个排列，暴力做总复杂度 $\mathcal O(qn^2)$，A 性质下 $\mathcal O(n^2+q)$，期望得分 $15$。

通过该做法可以证明 $b$ 数组对应唯一的合法排列 $p$，两者能形成双射，题面里的最小值是诈骗。

Sol.3

数据结构加速 Sol.2 的过程，比较容易的是倒着确定值，用权值线段树 / 树状数组上二分即可。总复杂度 $\mathcal O(qn\log n)$，A 性质下 $\mathcal O(n\log n)$，期望得分 $40$。

Sol.4

注意到只询问单个位置，求出整个排列有点浪费。只关注 $p_i$ 的值，从前 $i$ 个数开始不断向后扩展，维护当前 $p_i$ 的相对排名 $x$，初始为 $b_i+1$。加入位置 $j$ 时，若 $b_j\ge x$ 则 $x$ 不变，否则 $x$ 加一，这样最终得到的 $x$ 即为答案。总复杂度 $\mathcal O(nq)$，期望得分 $45$，拼上 Sol.3 做 A 性质期望得分 $55$。

Sol.5

数据结构加速 Sol.4 的过程。注意到 $j$ 位置会将 $x\gt b_j$ 的 $x$ 加一，增加量是分段一次函数。线段树维护区间一次函数复合，则长为 $len$ 的区间一次函数至多有 $(len+1)$ 段，且必然单调不降。将信息压到段数级别，维护 $a_i$ 表示函数中加 $i$ 的最小 $x$ 值，$a$ 是长为 $\mathcal O(len)$ 的单调不降数组。查询时在 $a$ 上二分即可。

考虑将 $f,g$ 合并得到 $h$，根据定义有 $h_i=\min_{j=0}^{i}(\max(f_j,g_{i-j}-j))$。有结论：令 $h_i$ 取最小值的 $j$ 为 $t_i$，则 $t$ 是单调不降的，即 $t_i\le t_{i+1}$。证明考虑首先 $h_i$ 不降，因为 $f_j$ 不变且 $g_{i-j}$ 随 $i$ 增大而增大。之后求 $h_{i+1}$ 可从 $x=h_i$ 开始枚举 $x$ 并检查是否合法，方式为取 $f_j\le x$ 的最大 $j$，看 $\max(f_j,g_{i-j}-j)$ 是否不超过 $x$。在该过程中用于检查的 $j$ 不会低于 $t_i$，于是 $t_{i+1}\ge t_i$。

有了上述结论，用指针维护当前最优的 $j$，可 $\mathcal O(len)$ 合并出长为 $len$ 的数组 $h$。于是线段树维护区间信息，单点修改时从叶子修改到根，单次复杂度 $\mathcal O(n)$。查询时依次在对应的 $\mathcal O(\log n)$ 个节点上二分，单次复杂度 $\mathcal O(\log ^2n)$。总复杂度 $\mathcal O(qn)$，A 性质下 $\mathcal O(n\log n+q\log^2 n)$，期望得分 $55$。

另外其实有更强结论：$t_{i+1}\in\{t_i,t_i+1\}$，证明需观察 $h_i$ 的结构，由于最小值必取在单增的 $f_j$ 和单减的 $g_{i-j}-j$ 交点处，讨论交点两侧大小关系即可证明。用该结论会略微降低实现难度和常数，不太重要。

Sol.6

对于这种修改查询复杂度不平衡的情况，可以使用分块平衡。具体地，每 $B$ 个位置分一块，每块开线段树维护整块函数信息，单点修改复杂度降到 $\mathcal O(B)$；查询时暴力跳所在块内元素，再依次在后面块上线段树根节点二分，查询复杂度为 $\mathcal O(B+\frac{n}B\log B)$，平衡取 $B=\sqrt{n\log n}$ 即有复杂度 $\mathcal O(q\sqrt{n\log n})$，期望得分 $100$。实际上由于线段树的大常数和 upper_bound 的小常数，$B$ 取小一点会跑得更快。

另外使用双指针或分散层叠似乎可以做到单根号，不过常数应该不小，意义不大。

后记

感谢推荐 / 提供了前两题的小 X，进行了部分验题的小 S，以及一起讨论 T2 证明的小 W、小 C 和小 D。

MOCKER44. 好听。SSP 是其外号 烧诗P 的缩写，并非费用流算法。SSP Round 1 可在此处查看。

最后祝大家春节快乐！之后都能 rp++！

爆竹鸣响长夜未已

飞鸟衔新叶回巢

归乡自天涯海角

山间的小路它也此刻往来热闹

齐思量出游相邀

共祝来年节节高

结彩串巷共迎灯宵

——MOCKER44. / 洛天依《游春》

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-30 12:00:11

我的痛苦不断在反复

生命就是硬走下这一条血路

请你不要落泪或是为我而恸哭

用失败欢呼

用烈火阐述

把你骄傲送入坟墓

——《“血路”》

Day.-2（11.26）

几天前被甲流击倒了，在家歇着。

于是没去学校参加赛前动员活动，但在线上参与了蜂鸟合唱，爽了；但是有延迟，不爽了。

Day.-1（11.27）

还在家，鼓起勇气重做了击败我的 CSP 后两题。

我草怎么知道 T4 大体思路还做不出，红温了，看题解去了。

我草我读错题了，没有人类了，怪不得当时场上暴力都没写出来。

不过早就过去了，这种时候得知真相反倒更加释怀了。

Day.0（11.28）

上午还在家，三个小时速通了洛谷板子赛。

中午在服务区拦截了学校大巴，跟着一块到了酒店。

然后神人 chb 用智能音箱和电视大放 True Music，声音大到吵到了隔壁的曹神，无敌了。

晚上试机，同考场五个同校的？wfyz 蒸蒸日上啊。拍了个线段树就跑路了。

其余时间基本全在打塔，胡局忘防被心脏重击爆了，当攒 rp 了。

流感没完全好，本来想早睡来着，但还是拖到了十一点，不过睡得很好。

可这一瞬间你看见烟花在天空绽放

已不是触不及的远方

在这份悲伤盛开过后

你的心定能再次跳动

我知晓你还不应死去在今天

还要由花知晓春去秋来

——《无人愿聆听的歌》

Day.1（11.29）

进场前比较紧张，毕竟 NOIP 挺重要的，也怕自己再出现 CSP 那种失误。不想死在这场比赛。

开场，大体浏览了一下，感觉结构跟去年很像啊。T1 这不是随便调整，跟去年比不了吧，十来分钟过了。

看 T2，读错题写了个神秘东西，过不了样例 1，遂发现读错了。还好只浪费了十来分钟，问题不大。之后就想到了做法，然而看起来就复杂完了。由于有 CSP 的前车之鉴，又冷静分析了一下，感觉确实想不出更好的做法了，于是开始写。

这个分讨 + 组合式子有点复杂的，越写越红温。一直告诉自己要冷静，推推写写修到十点多才过样例 1，然后样例 2 爆了。这下真红温了，于是上了个厕所冷静头脑，回来对着调了几个细节才过，此时大概十一点。

然后 T3T4 都想了想，胡出来了 T3 $\mathcal O(n^4)$ 的树形 DP，常数还很小。由于 CSP 的教训，决定直接开写。写完发现 $120$ 都跑不了？原来是删代码漏删了两重循环，难绷。我去怎么 $360$ 跑这么快，那可能有 $48$ 了啊。

然后时间不多了，于是决定直接拼好分，把 T4 的 $\mathcal O(n^2q)$ 和 AB 性质都写了。最后还剩半小时，发现 T3 加前缀优化之后能改成 $\mathcal O(n^2m)$，常数小点的话甚至能冲 $68$，前面的 $48$ 也会更稳。于是留了个备份就开始优化，结果可能是预处理之类的细节挂了，最后没调出来，怕常数变大也没改 vector 开数组冲 $m$ 较小的分。

快结束的时候自己复盘了一下，感觉自己这场的表现跟去年很像啊，都是过了前两题然后拼好分。不过今年 T1 简单不少，T2 难一些。预估 $100+100+[32,48]+40$，不挂的话至少不会退役了。

我们 终究会走散

他们 也不过虚幻

捻一抹红妆的她 还在追

泪花 转啊转

转不回来 她要的以为

重岩叠对

早已看不见 的那份纯粹

和曾经那个孩子 说再见吧

——《樱桃簪子》

然后出场了，发现一车人被 T2 创飞，T3 很多人甚至不会多项式复杂度。这么看我分竟然还不低？不过同校高一选手似乎都有点寄，同级也有没发挥好的。看了看 QQ 发现很多大手子也寄了，T2 还是太吃心态了。别笑，你来你也过不了第二关。

又去了去年那家烧烤店吃饭，感觉比去年人多了些，还是那句话，wfyz 蒸蒸日上啊。

晚上回家复现了下 T3，想看看能过多少，结果怎么全 WA 了？给我吓一跳，然后发现 $res$ 忘初始化了，赛时肯定写了。改完过了 $48$，不过发现代码里可能访问了 $-1$ 下标，希望没啥大问题吧。

读了不少游记，好多熟人都被创飞了，感觉因为抽象题在 NOIP 不幸退役非常可惜，也对好朋友们非常不舍。或许是比较幸运，我应该能继续备战省选，之后大概率还在 LCA 营训。最后祝大家，也祝我自己一切顺利吧。

我们

跌跌撞撞 寻觅一个方向

忘却了 禁锢思绪 还在过往挣扎

追逐着月亮 模糊了面颊

不在意 明天是否还有太阳

——「追逐月光」feat.诗岸

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-21 08:01:46

题意

给定一个带颜色的括号序列，要求选出一个匹配子序列，使得相邻或匹配的括号颜色不同，求能选出的本质不同合法子序列数量。$n\le 700$。

题解

如果是下标不同子序列，可以设 $f_{l,r}$ 表示在 $[l,r]$ 内选，强制选 $l,r$ 且内部合法的方案数，之后区间 DP 转移。对于本质不同子序列，考虑最小表示，即对于某种子序列，每一位都尽可能靠前选。这样会限制选的相邻位置 $x,y$ 满足 $pre_y\le x$，其中 $pre_y$ 表示 $y$ 上次出现的位置。这样是局部限制，可在 DP 过程中满足，最终也只对不存在 $pre_l$ 的 $f_{l,r}$ 统计答案即可。

考虑转移，分为 $l,r$ 匹配和不匹配两种。前者枚举内部选的左右端点 $x,y$ ，不要求 $x,y$ 匹配，限制为 $c_l\ne c_r,c_l\ne c_x,c_r\ne c_y,pre_x\le l,pre_r\le y$；后者枚举与 $l$ 匹配的 $x$，再枚举 $x$ 后第一个左括号 $y$，要求 $l,x$ 匹配，不要求 $y,r$ 匹配，限制为 $c_l\ne c_x,c_x\ne c_y,pre_y\le x$。对于要求匹配的限制，额外开一维 $0,1$ 表示是否强制匹配即可，复杂度 $\mathcal O(n^4)$，常数很小。

尝试优化，发现对于方案中相邻的 $x,y$，固定 $y$ 时后缀 $x$ 合法，但固定 $x$ 时合法的 $y$ 没有规律，似乎不太容易直接前缀和优化。注意到转移时 $y$ 的限制只与 $x,r$ 有关，于是设 $g_{x,r},h_{x,r}$ 分别表示固定 $x,r$ 时，两种转移的合法 $y$ 对应值之和。此时 $f_{l,r,1}$ 只会贡献到 $g_{l,t}$ 和 $h_{t,r}$，也就是 $\mathcal O(n)$ 个值中。转移时枚举 $x$ 后可以 $\mathcal O(1)$，于是总复杂度为 $\mathcal O(n^3)$，好像常数还是不大啊。

代码

见云剪切板。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-20 16:38:20

怎么题解区全是线段树，这个应该好写一些。

题意

$n$ 条射线绕中心形成一个环，有 $m$ 条连接相邻两射线的线段，两端点到中心距离相等。初始选择某射线向外走，遇到线段时强制走到另一端。可以任意加入满足同样限制的线段，对每个 $i$ 求初始在 $i$ 射线上走，最终走到 $s$ 射线无穷远处需要加入的最少线段数。$n\le 2\times 10^5,m\le 5\times 10^5$。

题解

由于是强制走过线段，若按到中心的距离从大到小考虑，则每条线段相当于交换相邻两条射线的终点编号，要求即最终 $i$ 射线终点为 $s$。考虑按该顺序 DP，设 $f_{i,j}$ 表示考虑了前 $i$ 条给定线段，当前 $j$ 射线终点为 $s$ 的最小加入数，有初始值 $f_{0,i}=\min(\left|s-i\right|,n-\left|s-i\right|)$。

至于转移，先交换 $f_{i-1,t_{i}},f_{i-1,t_{i}\bmod n+1}$。之后还要考虑线段的加入，有 $f'{i,j}=\min f{i-1,k}+\min(\left|j-k\right|,n-\left|j-k\right|)$。由于只有两个位置变化，只需要尝试用较小值向外更新，并尝试更新较大值，可以做到单次 $\mathcal O(n)$，总复杂度 $\mathcal O(nm)$，答案即 $f_{m,i}$。

观察这个 DP 的形式，注意到差分数组只有 $-1,0,1$，否则一定可以更新，于是考虑维护差分数组 $g_i=f_{i}-f_{(i+n-2)\bmod n+1}$。设 $x=t_i,y=t_i\bmod n+1$，$g_y=0$ 时交换没有影响，以下以 $g_y=1$ 为例，$g_y=-1$ 是类似的。

首先考虑 $x$ 位置的变化，$f_x$ 先由于交换增加 $1$。此时若 $g_x=1$，则 $f_x$ 还会被上个位置拉回来，于是 $g_x$ 仍为 $1$，$g_y$ 变成 $0$；否则就拉不回来了，$g_x$ 增加 $1$，$g_y$ 变成 $-1$。至于 $y$ 减小对其他位置的影响，显然无法更新前面元素，画图可得从 $y$ 向后找到首个非 $1$ 位置 $z$，此前的 $f$ 值均会减一，在 $g$ 上的影响即 $g_z$ 增加 $1$。

这需要查询 $y$ 后面首个非 $1$ 位置，在 $g_y=-1$ 时是前面首个非 $-1$ 位置，用 set 分别维护两种下标，单点改的时候也修改 set 即可。另外若只考虑给定操作会将 $s$ 交换到 $t$，则一定有 $f_{m,t}=0$，从该位置按 $g$ 数组推出 $f$ 即为答案，复杂度 $\mathcal O(m\log n)$。

代码

#include<bits\/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,s,f[N],g[N]; pair<int,int> a[N];
set <int> sa,sb;
void cg(int p,int x)
{
	if(g[p]==1&&x!=1) sa.insert(p);
	if(g[p]!=1&&x==1) sa.erase(p);
	if(g[p]==-1&&x!=-1) sb.insert(p);
	if(g[p]!=-1&&x==-1) sb.erase(p);
	g[p]=x;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++) cin>>a[i].first>>a[i].second;
	for(int i=1;i<=n;i++) f[i]=min(abs(i-s),n-abs(i-s));
	sort(a+1,a+1+m);
	for(int i=1;i<=n;i++)
	{
		g[i]=f[i]-f[(i+n-2)%n+1];
		if(g[i]!=1) sa.insert(i);
		if(g[i]!=-1) sb.insert(i);
	}
	for(int _=m;_;_--)
	{
		int x=a[_].second,y=x%n+1;
		if(s==x||s==y) s=(s^x^y);
		if(!g[y]) continue;
		if(g[y]==1)
		{
			int z=-1; auto it=sa.upper_bound(y);
			if(it!=sa.end()) z=*it;
			else z=*sa.begin();
			cg(z,g[z]==0);
			if(g[x]==1) cg(y,0);
			else cg(y,-1),cg(x,g[x]==0);
		}
		else
		{
			int z=-1; auto it=sb.lower_bound(y);
			if(it!=sb.begin()) z=*prev(it,1);
			else z=*prev(sb.end(),1);
			cg(z,g[z]?0:-1),z=y%n+1;
			if(g[z]==-1) cg(y,0);
			else cg(y,1),cg(z,g[z]?0:-1);
		}
	}
	f[s]=0;
	for(int i=s;i>1;i--) f[i-1]=f[i]-g[i];
	for(int i=s+1;i<=n;i++) f[i]=f[i-1]+g[i];
	for(int i=1;i<=n;i++) cout<<f[i]<<'\n';
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-19 13:31:04

11.12 图论

• 局部：枚举最小图，按照是否含有该局部将所有图分类。

比如平面图不含 $K_5,K_{3,3}$，半平面图不含 $K_4,K_{2,3}$。

• 生成树（DFS 树 / BFS 树 / 最小生成树）

杂题

题意

定义单点合法，若干个合法图放在一起合法，合法图对边取补集合法。给定无向图，判断该图是否合法。$n,m\le 10^5$。

题解

将定义过程倒过来，每次从原图和补图中选一个，递归进每个连通块分别判断。注意到原图和补图至少有一个连通，对这个图拆连通块递归下去。这需要对原图和补图分别进行搜索，原图显然可以 $\mathcal O(m)$ 搜索，对于补图可以 BFS，使用链表维护所有没搜过的点，这样额外复杂度是所有点度数之和，也是 $\mathcal O(m)$ 的。

分析一下复杂度，有 $T(m)=\mathcal O(m)+T(m-\sqrt m)$，这样的话总复杂度为 $\mathcal O(m\sqrt m)$。至于为啥能使边数减少 $\sqrt m$，首先每次所用的图一定是上次的补图，于是每两轮就会用一次原图的补图。而每次用原图的补图划分连通块时，上轮同一连通块内的边若两端被划分进了不同连通块，则之后就没用了。感性理解这个过程中废弃的边是比较多的，因为不同连通块间的完全 $k$ 部图边全没了。具体不会证，没题写不了，不管了。

P11762 [IAMOI R1] 走亲访友

题意

给定 $n$ 点 $m$ 边连通无向图，要求走一条从 $s$ 出发长不超过 $k$ 的路径，走的过程中可以选择删掉经过的边，走完后未删除的边形成一棵生成树。$n\le 1000,m\le \frac {n(n-1)}2,k=n+m$。

题解

由于要求保留生成树，直接先跑出一棵来，不妨以 $s$ 为根，现在要求路径经过非树边至少一次，这应该是欧拉路径状物，为方便直接做欧拉回路，这样要求每个点度数均为偶数。初步想法是树边可以不走，于是决策一下树边是否经过就可以满足度数限制了，然后做到了路径长度不超过 $m$？

并非，因为欧拉回路还需要图连通，而断掉若干树边后图不一定连通了。于是每条树边也得经过至少一次，在此基础上决策若干树边多走一次即可。路径长度不超过 $n+m-1$，复杂度 $\mathcal O(n+m)$。

典题

• 给定无向图，求所有点度数均为偶数的边生成子图个数。

找一棵生成树，非树边任意选之后合法树边是存在且唯一的，于是一个连通图方案数为 $2^{m-n+1}$，总方案数为 $2^{m-n+k}$，其中 $k$ 为连通块个数。

• 给定无向图，求所有点度数均为奇数的边生成子图个数。

若连通图点数为奇数，则方案数一定为 $0$，否则方案数仍为 $2^{m-n+1}$，推理相同。总方案数为 $2^{m-n+k}$ 或 $0$，且只在存在点数为奇数的连通块时为 $0$。

• 给定无向图，每个点限制度数为偶数 / 奇数 / 无限制，求满足条件的生成子图个数。

对于一个连通图，若所有点均有限制，直接判断总度数是否为偶数即可，是则答案为 $2^{m-n+1}$，否则为 $0$。若存在点无限制，考虑枚举每个点度数奇偶性，一定恰有一半方案奇偶性是对的。设存在 $t$ 个无限制点，则方案数为 $2^{m-n+t}$，将所有连通块的答案乘起来即可。

P7624 [AHOI2021初中组] 地铁

题意

有一个环，要求相邻点距离为正整数，有 $m$ 条 $u,v$ 顺时针距离不小于或不大于 $w$ 的限制，求合法环长个数。$n,m\le 500$。

题解

考虑如何判断环长 $x$ 是否合法，可以把限制建成差分约束，只要没有负环就存在解。此时 $u\lt v$ 的限制只有值，而 $u\gt v$ 的限制里含 $x$。考虑对于图中的一个环，若 $x$ 的系数和为正则限制 $x$ 为一个后缀，为负则限制 $x$ 为一个前缀，这说明合法 $x$ 形成一个区间。

于是二分，对于 $x=mid$ 跑差分约束，若存在负环再判一下环上系数和，从而实现找到合法区间左右端点。注意此处途径边数超过 $n$ 的点不一定在负环上，也可能在负环延伸出去的链上，所以要先跳 $n$ 次前驱再求负环。总复杂度 $\mathcal O(nm\log V)$。

P3645 [APIO2015] 雅加达的摩天楼

题意

$n$ 个点上有 $m$ 个人，每个人有参数 $d$，从 $p$ 点可移动到 $p+d,p-d$ 之一。现要从 $0$ 传递情报到 $1$，只有拿到情报的人才能移动，求最少移动次数。$n,m\le 3\times 10^4$。

题解

考虑暴力，从 $p$ 向 $p+kd$ 连权为 $\left|k\right|$ 的边后直接跑最短路即为答案。可以优化建图，令 $B=\sqrt n$，则所有 $d\gt B$ 的边共 $\mathcal O(m\sqrt n)$ 条。对于 $d\le B$ 的边，按 $d$ 和 $p\bmod d$ 分类，每类中向前的边连到上一个有人的点即可，于是每类有 $\mathcal O(\frac nd)$ 条边，共 $d$ 类，总边数为 $\mathcal O(n\sqrt n)$。这样只能跑 Dijkstra，可能要带个 log，没有写。

考虑换一种方式，设 $f_{i,d}$ 表示当前参数为 $d$ 的人在 $i$ 点需要的最少移动次数。$d\le B$ 的状态数不超过 $\mathcal O(n\sqrt n)$，$d\gt B$ 的状态数不超过 $\mathcal O(m\sqrt n)$，总状态数是有保证的。另外这样转移只有在某个点上转到别的人，或者向前后跳一步，边权只有 $0,1$，可以 $01$ BFS 解决，复杂度 $\mathcal O((n+m)\sqrt n)$。

11.12 思考题 复读机

以下问题中给定一个序列，可以重复读入，但只有 $\mathcal O(1)$ 内存。序列中的值均为正整数。（当然原题是自然数，此时给所有数加上 $1$ 即可）

• 序列中只有一种数出现奇数次，找出这种数。

直接求序列所有值的异或值即为答案，读入 $1$ 遍，记录 $1$ 个数。

• 序列中只有两种数出现奇数次，找出这种数。

确定性算法：先求出所有值的异或值 $x\oplus y$，找到其中某个 $1$，按照这一位的值分成两个集合，对两个集合各做一种数的情况即可，这可以在同一遍读入中求。读入 $2$ 遍，记录 $2$ 个数。

非确定性算法：每轮可通过哈希将所有种类的值随机分成 $c$ 个集合，只要 $x,y$ 分到不同集合就能求出答案，错误率 $\frac 1c$。可以进行常数 $t$ 轮，多轮求解可在同一遍读入中求，读入 $1$ 遍，记录 $tc$ 个数，错误率 $\frac 1{c^t}$。一般来说 $c$ 取距 $e$ 最近的整数 $3$ 最优。

还有一种做法，准备 $2k$ 个集合，其中 $k$ 为奇数。设计一个函数 $f(x)$，返回 $[1,2k]$ 的一个大小为 $k$ 的子集，将该子集内的集合值均异或上 $x$。这样当且仅当 $x,y$ 随机出来的子集完全相同时求不出答案，否则可以通过 $x,y,x\oplus y$ 中 $x,y$ 出现次数相同求出答案。读入 $1$ 遍，记录 $2k$ 个数，错误率 ${2k\choose k}^{-1}$。LCA 说这种方法已经接近信息论的错误率下界了，不懂。

• 序列中只有两种数出现次数不为 $3$ 的倍数，找出这种数。

首先若只有一种数出现次数不为 $3$ 的倍数，可以直接在三进制下每一位求和再对 $3$ 取模，再按 $c_x\bmod 3$ 分讨即可，这个值与 $n\bmod 3$ 相等。读入 $1$ 遍，记录 $1$ 个数。

确定性算法：将所有值转化为二进制，记录每个二进制位 $1$ 的个数对 $3$ 取模的结果。之后可以根据 $c_x+c_y\equiv n\pmod 3$ 分讨，找到某个 $x,y$ 不同的二进制位，再按这一位分组进行一种数的情况，同样可以同一遍求。读入 $2$ 遍，记录 $2$ 个数。

非确定性算法：与上个题次数奇偶性的做法相同，可能会多一些对出现次数的分讨，记录数字个数可能要乘上一个常数，不再赘述。

U498564 找不同

题意

给定长为 $2n+3$ 的序列，其中 $n$ 种数出现两次，$3$ 种数只出现一次。只有 $\mathcal O(1)$ 空间，找出只出现一次的三种数，序列输入四次。$n\le 7\times 10^5$。

题解

考虑分离出一个数，转化成两种数的情况。将序列所有值异或起来可得 $X=x\oplus y\oplus z$，定义 $b_i=a_i\oplus X$，则 $b$ 中出现奇数次的只有 $x\oplus y,x\oplus z,y\oplus z$ 三个数。显然三者两两不同，且异或值为 $0$，这说明每个二进制位上均全 $0$ 或恰有两个 $1$。

于是考虑最低位的 $1$，设 $x$ 最低位的 $1$ 为 $f(x)$。根据上面的结论，三个数的 $f$ 值恰有两个相同。于是先求出全局 $f$ 值的异或和，就得到了其中一个数的 $f$ 值 $Y$。按照 $f$ 值是否等于 $Y$ 将序列分成两部分，各有 $1,2$ 个出现一次的数，套用上面的做法即可。读入 $4$ 遍，粗糙实现可以记录 $7$ 个数。

LOJ6537. 毒瘤题加强版再加强

题意

给定长为 $n$ 的序列，其中恰有 $k$ 个数出现奇数次。只有 $\mathcal O(1)$ 空间，找出这 $k$ 个数。$n\le 3\times 10^6,k\le 5000$，空间限制 3MiB。

题解

太难了，直接考虑非确定性算法。考虑设计哈希函数 $f(x)$，开 $t$ 个大小为 $\mathcal O(m)$ 的哈希表，每输入一个 $x$ 就向所有哈希表的 $f(x)\bmod m_i$ 位置异或上 $f(x)$。最后取出哈希表所有未冲突位置的值 $f(x)$，将其转换回 $x$ 输出。

首要问题是，需要设计一个这样的函数 $f$，需要大致随机，能以较高正确率判断一个值是否是该函数值，且能快速转换回 $x$。采用 $f(x)=kx+b$，$k$ 取大质数，这样判断 $y$ 就可以检查 $y\bmod k$ 的值是否为 $b$ 了，转换回 $x$ 只需要除以 $k$ 下取整即可。

这样就得到了一个算法。分析一下错误率，需要 $k$ 个数均被找到，这需要每个数都在 $t$ 个哈希表中的至少一个不冲突，单个冲突概率为 $\mathcal O(\frac km)$，于是单个数正确概率约为 $1-(\frac k m)^t$，于是正确率为 $(1-(\frac km)^t)^k$，当然这是忽略哈希值转换错误率的结果。对于本题，大概可以取 $t=7,m=30000$，有 $0.98$ 左右的正确率。

11.14 字符串

问题：

• 子串匹配

• 子串约束（Border / 周期、回文）

• 其他（子序列等）

算法：自动机（字典树）、“莫队”思想、Hash。

用 Trie 树刻画字符串集合，若只判断某串是否在集合内，可以按未来可以走的串缩等价类得到 DFA。同样用 DFA 刻画所有包含串 $S$ 的串，自动机的不同状态分别为串后缀为 $S$ 前缀的长度。

考虑转移，发现关心 $S$ 所有前缀的 Border。注意到一个串的 Border 由于传递性具有全序，于是记录最大真 Border 即可。然后就发明了 MP 算法，当然这也就是一般说法中的 KMP。若预处理 $tr_{i,j}$ 表示状态 $i$ 加上字符 $j$ 到的状态，就得到了 KMP 自动机（Trie 图）。

有一些结论，比如最大周期等于长度减最小 Border 之类，手推可知。

若求多个前缀的公共 Border，可在失配树上求 LCA。扩展到多串变成 AC 自动机了，超纲。使用“莫队”思想还可以推出扩展 KMP 和 manachar，略过不表。

Hash，$B,P$ 取质数，也可以将每种字符随机映射之后计算，在减法之类的东西上有奇效。一般来说要使得哈希空间比比较次数的平方略大，双哈希一般够了。集合哈希可以使用异或之类。其他哈希可以尽量转化成序列或集合哈希。

LOJ502. 「LibreOJ β Round」ZQC 的截图

没太懂这个题，之后可能会做。

P12009 【MX-X10-T5】[LSOT-4] Masuko or Haru？

一顿转化之后需要对每个连通块维护根节点对于所有串的 $0/1$ 信息，在这里使用哈希。之后应该会做。

11.19 组合计数

判定型计数（唯一判定、最小表示、取补集、容斥拆贡献）

“证书”定义为某种使方案合法的方案，最小表示即找到某个特定“证书”并对其计数，取补集即统计无“证书”的方案数。

考虑局部信息，大概意思是判定相邻元素合法，从而整个方案合法。

CF559C Gerald and Giant Chess

题意

给定长宽分别为 $h,w$ 的网格，有 $n$ 个障碍，求从左上到右下不经过障碍的路径条数。$h,w\le 10^5,n\le 2000$。

题解

考虑取补集。考虑设 $f_{i}$ 表示不经过其他障碍走到 $(x_i,y_i)$ 的方案数，初值为 ${x_i+y_i-2 \choose x_i-1}$。另外对于所有 $x_j\le x_i,y_j\le y_i$ 的 $j$，要减掉实际上首个障碍为 $j$ 的方案数，即 $f_i\leftarrow f_i-f_j\times {x_i-x_j+y_i-y_j\choose x_i-x_j}$。最后用 $h+w-2\choose h-1$ 减掉所有 $f$ 的和即可，复杂度 $\mathcal O(\max(h,w)+n^2)$。

P11588 [KTSC 2022 R2] 彩色括号序列

题意

给定一个带颜色的括号序列，要求选出一个子序列，使得相邻括号和匹配括号颜色均不同，求能选出的本质不同合法子序列数量。$n\le 700$。

题解

如果是下标不同子序列，可以设 $f_{l,r}$ 表示在 $[l,r]$ 内选，强制选 $l,r$ 且内部合法的方案数，之后区间 DP 转移。对于本质不同子序列，考虑最小表示，即对于每种子序列，每一位都尽可能靠前选。这样会限制选的相邻位置 $x,y$ 满足 $pre_y\le x$，其中 $pre_y$ 表示 $y$ 上次出现的位置。这样是局部限制，可以在 DP 过程中满足，最终只对不存在 $pre_l$ 的 $f_{l,r}$ 统计即可。

考虑转移，分为 $l,r$ 匹配和不匹配两种。前者枚举内部选的左右端点 $x,y$ ，不要求 $x,y$ 匹配，限制为 $c_l\ne c_r,c_l\ne c_x,c_r\ne c_y,pre_x\le l,pre_r\le y$；后者枚举与 $l$ 匹配的 $x$，再枚举 $x$ 之后第一个左括号 $y$，要求 $l,x$ 匹配，不要求 $y,r$ 匹配，限制为 $c_l\ne c_x,c_x\ne c_y,pre_y\le x$，复杂度 $\mathcal O(n^4)$，常数很小。

注意到对于方案中相邻的 $x,y$，固定 $y$ 时后缀 $x$ 合法，但固定 $x$ 时合法的 $y$ 没有规律，似乎不太容易直接前缀和优化。注意到转移时 $y$ 的限制只与 $x,r$ 有关，于是设 $g_{x,r},h_{x,r}$ 分别表示固定 $x,r$ 时，两种转移的合法 $y$ 对应值之和。此时 $f_{l,r,1}$ 只会贡献到 $g_{l,t}$ 和 $h_{t,r}$，也就是 $\mathcal O(n)$ 个值中。转移时枚举 $x$ 后可以 $\mathcal O(1)$，于是总复杂度为 $\mathcal O(n^3)$，好像常数还是不大啊。

P14364 [CSP-S 2025] 员工招聘

暂时不想做这题，没听。或许 NOIP 前会回来补掉。

• 子集容斥

有 $n$ 条限制，求所有限制均满足，即不合法限制集合为空集的方案数，当容易算某子集强制不合法，其余不作限制的方案数时可使用子集容斥。

具体地，枚举集合 $S$ 内的限制均不满足，设 $f(S)$ 表示方案数，则答案为 $\sum (-1)^{\left|S\right|}f(S)$。

P6076 [JSOI2015] 染色问题

题意

给定 $n\times m$ 网格和 $c$ 种颜色，要求每行每列不能全无色，且每种颜色均出现，求方案数。$n,m,c\le 400$。

题解

直接子集容斥，枚举 $i,j,k$ 表示 $i$ 种颜色不出现，$j$ 行 $k$ 列全无色，答案为 $\sum {i\le c}(\sum{j\le n}(\sum_{k\le m} (c-i+1)^{(m-k)(n-j)}\times (-1)^k\times {m\choose k})\times (-1)^j\times {n\choose j})\times (-1)^i\times {c\choose i}$，也就是 $\sum_{i\le c,j\le n,k\le m} (c-i+1)^k\times {c\choose i}\times{n\choose j}\times {m\choose k}\times (-1)^{i+j+k}$，枚举 $i$ 后先预处理 $(c-i+1)$ 的若干次方即可做到 $\mathcal O(nmc)$。

或者可以只容斥两层，对于最后一层不枚举 $k$，而是直接计算出 $(c-i)$ 种颜色填 $(n-j)\times m$ 网格的方案数，要求每列不全无色，答案为 $((c-i+1)^{(n-j)}-1)^m$，再套上前两层的容斥系数即可，这里好像只能快速幂了，复杂度 $\mathcal O(cn\log m)$。

P1450 [HAOI2008] 硬币购物

题意

给定四种钱币，价值分别为 $c_i$。$q$ 次询问给出 $d_i,m$，表示有 $d_i$ 个价值为 $c_i$ 的钱币，求和为 $m$ 的方案数。$q\le 1000,c_i,d_i,m\le 10^5$。

题解

所用个数不超过 $d_i$ 有点难做，考虑容斥变成所用个数超过 $d_i$。具体地，枚举 $S$ 内的种类一定超出限制，其余任意。求出 $S$ 内 $c_i(d_i+1)$ 的和，若其不超过 $m$ 则方案数为 $f_{m-s}$，其中 $f$ 为任意取所有钱币的方案数，可以提前完全背包预处理。总复杂度为 $\mathcal O(km+q\times 2^k)$，本题中 $k=4$。

• 二项式反演

大概是若有 $b_i=\sum_{j\le i} a_j\times {i\choose j}$，则 $a_j=b_j-\sum_{j<i} a_j\times{i\choose j}$，可以顺序求出。

• min-max 容斥

式子是 $\min_{x\in S} x=\sum_{T\in S}(\max_{x\in T} x)\times (-1)^{\left|T\right|+1}$，两者反过来也是成立的，证明可以考虑只有空集的偶数子集比奇数子集多一个，其余集合的奇偶子集数量相同。感觉主要应用是求期望啊。

• 点边容斥

对于统计合法连通块数量，枚举所有点统计并对方案数求和，再枚举所有边中点统计并减去方案数的和，这样每个连通块会被统计点数减边数次，次数恰为 $1$。

比如在圆方树上令圆点为 $-1$，方点为点双点数，$u,v$ 路径经过的所有点双点的并集（不包括 $u,v$）大小即为圆方树上路径和。

• 反射容斥

大概是在坐标系里将不合法的路径反射回去，变成两种路径数相减，典型应用是卡特兰数。

有一些拓展，比如有上下界限制时可以套多次反射容斥，状态数大概是 $\mathcal O(\frac nm)$ 的，其中 $m$ 为上下界之差。

P4769 [NOI2018] 冒泡排序

转化转化之后变成不存在三元下降子序列，然后画画图发现所有逆序对之间要递增，大概能用卡特兰数计算，之后可能会做。

下面这题是 LCA 讲思考题的时候讲的，由于这个思考题的前缀和差分比较基础，不开新标题了。

CF1097F Alex and a TV Show

题意

维护 $n$ 个可重集，支持将 $x$ 集合变为 $y,z$ 集合的并或者 $y,z$ 集合两两 GCD 形成的可重集，单点修改一个集合为单值集合，查询某集合内某数出现次数奇偶性。$n\le 10^5,q\le 10^6,v\le 7000$。

题解

由于只关心奇偶性，个数 $a_{i,j}$ 之类均对 $2$ 取模存储即可。另外由于有变为两集合 GCD 的操作，考虑记录 $b_{i,j}=\sum_{j\mid k}a_{i,k}$，这样合并操作即 $b_{x,j}=b_{y,j}b_{z,j}$，取并集时即 $b_{x,j}=b_{y,j}+b_{z,j}$，用 bitset 按位与和按位异或即可。

对于修改为单值集合，可以预处理出所有 $x$ 对应的集合状态。对于查询，需要枚举所有 $x\mid y$ 且 $\mu(\frac yx)\ne 0$ 的位置异或和，也对每个 $x$ 预处理出这个即可。总复杂度大概是 $\mathcal O(v\log v+\frac{qv}w)$，可以通过。

11.21 组合计数

组合（双射）、代数（生成函数）。

某题

题意

给定 $n,a_{n+1}$，要求 $a_i\mid a_{i+1}$，求合法序列数量，并对每种 $a$ 序列的数字种类数分别计算方案数。$n\le 10^5,a_{n+1}\le 10^9$。Bonus：$a_{n+1}\le 10^{18}$。

题解

将 $a_{n+1}$ 分解质因数为 $\prod p_i^{k_i}$，之后每个质因子独立，且均满足次数不降，于是可分别求方案数再乘起来。对于 $k_i$ 来说方案数为 ${k_i+n\choose n}$，这是将 $k_i$ 分到差分数组的 $(n+1)$ 个位置的方案数，全乘起来即为答案 $f_n$。

至于出现 $i$ 种不同数的方案数，显然数字种类数不超过 $\mathcal O(\log V)$ 级别。考虑先求出 $g_i$ 表示选出长为 $i$ 的单增序列方案数，一定有 $f_n=\sum_i g_i\times {n-1\choose i-1}$，于是先求出 $f$ 的前 $\log V$ 项再反演回 $g$ 即可，$i$ 种数的答案即 $g_i\times {n-1\choose i-1}$。

但是 $a_{n+1}\le 10^{18}$ 没法分解质因数了，然而注意到本题做法只跟 $k_i$ 有关，于是枚举到 $\sqrt[3] V$ 后只剩至多两个大质数乘积，即只可能是 $p,p^2,pq$ 三种，前两种都是好判的，这样就能得到 $k$ 序列了。没题写不了。

P2401 不等数列

题意

给定 $n,m$，求 $m$ 对相邻值上升的 $n$ 阶排列个数。

Bonus：$n,m\le 10^5$，模数为质数。

题解

可以 $\mathcal O(n^3)$ DP，设 $f_{i,j,k}$ 表示填了 $i$ 个数，$j$ 个上升且 $i$ 的相对排名为 $k$ 的方案数，前缀和优化转移即可。注意到有 $j,k\le i$，常数比较小，可以过。

设 $f_{n,m}$ 表示答案，尝试递推，考虑排列中 $1$ 的位置，从而从 $n-1$ 阶排列推过来。由于放到开头或某个下降位置会使上升位置增加，放到结尾或某个上升位置时上升位置数不变，有 $f_{n,m}=(m+1)f_{n-1,m-1}+(n-m)f_{n-1,m-1}$，就 $\mathcal O(nm)$ 了。$f_{n,m}$ 称为欧拉数。

有恒等式 $x^n=\sum_m f_{n,m}\times {x+m\choose n}$，于是有 $f_{n,m}=\sum_{i=0}^m (-1)^i {n+1\choose i} (m+1-i)^n$，可以做 Bonus。有点困难，先不管了。

P3403 跳楼机

同余最短路，由于 $p$ 可达则 $p+x$ 一定可达，于是按对 $x$ 取模的结果分类，每一类找到最小的可达 $p$ 即可，这可以使用最短路求。通过同余最短路也可以证明小凯的疑惑一题。

[ARC147D] Sets Scores

题意

对于 $n$ 个集合 $S_i$，定义其合法当且仅当相邻两个集合对称差大小恰为 $1$。对所有合法的 $n$ 个集合，求所有数出现次数的乘积之和。$n,m\le 2\times10^5$。

题解

拆乘法贡献，即对每个值枚举某次出现的集合编号 $a_i$，这样的编号 $n$ 元组数量就是某种集合方案的答案。另外描述一种方案可以使用 $S_1,d_i$，其中 $d_i$ 表示 $i,i-1$ 的对称差。注意到对于某种 $a,d$ 序列，使其合法的 $S_1$ 存在且唯一。于是答案为 $a,d$ 序列的方案数乘积，即 $n^mm^{n-1}$。快速幂，$\mathcal O(\log n+\log m)$。

P1758 [NOI2009] 管道取珠

平方拆贡献，即对每个 $a_i^2$，将整个过程同时做两次，结果序列相同的方案数即为每种结果的方案数平方和，复杂度 $\mathcal O(n^3)$。

11.21 思考题 正难则反

• 求多少个 $n$ 阶排列 $p$ 满足不存在分界点 $1\le k\lt n$，使得 $\forall i\le k,j\gt k,p_i\lt p_j$。

设 $f_n$ 表示 $n$ 阶排列的答案，考虑取补集，枚举第一个合法分界点 $j$，则有 $\sum_{j<i}f_j\times (i-j)!+f_i=i!$，于是 $f_i=i!-\sum_{j\lt i}f_j\times (i-j)!$，可以 $\mathcal O(n^2)$ 求出。

• 求有多少个点数为 $n$ 的有标号无向简单连通图。

设 $f_n$ 表示 $n$ 个点的答案，仍然取补集，枚举 $1$ 所在的连通块大小，则有 $\sum_{j\lt i} f_j\times 2^{i-j\choose 2}\times {i-1\choose j-1}+f_i=2^{i\choose 2}$，还是可以 $\mathcal O(n^2)$ 递推出来。

• 求有多少个点数为 $n$ 的有标号无向简单边双连通图。

太困难，没有听懂，似乎需要 Prufer 序列 + 前缀和推一推。$n\le 10^5$ 版本是 P5828。

CF1750F Majority

题意

对于一个 $0,1$ 序列，每次操作可选择两个 $1$ 的位置 $l\lt r$，要求区间 $[l,r]$ 内的 $1$ 不少于 $0$，之后将该区间覆盖为 $1$。一个序列合法当且仅当可以通过该操作变为全 $1$，求长为 $n$ 的合法序列数量，对输入的 $m$ 取模。$n\le 5000$。

题解

首先考虑如何判断一个序列是否合法，发现可以不断任意操作，直到无法进行，可以注意到最终序列是唯一的。于是可以根据最终序列计数，同时考虑正难则反，尝试对不合法序列分类计数。

于是设 $f_{i,j}$ 表示长为 $i$ 且两端为 $1$ 的序列，且最终序列最后一段 $1$ 长为 $j$ 的方案数，答案为 $f_{n,n}$，根据总方案数有 $\sum f_{i,j}=2^{i-2}$。于是可以先求 $j<i$ 的部分，剩下的就是 $f_{i,i}$。转移考虑枚举上一段 $0$ 和再上一段 $1$ 的长度 $m,k$，有 $f_{i,j}=f_{j,j}\times \sum_{m\gt k+j} f_{i-j-m,k}$。

考虑优化转移，令 $p=i-j-m,m=i-j-p$，则有 $i-j-p\gt k+j$，即 $p+k\lt i-2j$。于是转化为 $f_{i,j}=f_{j,j}\times \sum_{p+k\lt i-2j} f_{p,k}$，后面这个容易前缀和优化，于是转移变成 $\mathcal O(1)$ 的，可以做到 $\mathcal O(n^2)$ 的复杂度。

[AGC067B] Modifications

CF1605F PalindORme

均为正难则反思想的应用，之后应该会做。

11.23 杂题

CF1543E、CF1548D2、CF1552E 被弃了，太抽象。

P13494 【MX-X14-T4】分门别类

二分，可以 $\mathcal O(n^2)$ DP 来 check。或者整体维护 DP，复杂度可以优化。之后应该会做。

CF1548C The Three Little Pigs

生成函数推导 / 组合意义推，可以得到递推式，之后应该会做。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-17 14:53:24

省流：打星，$5$ 题，银。

其实不省流这篇也很短。

雪间月下空自哀 但见一花开

也许 春见我梦里的期待

——wukino《只有春天，禁止入内》

Day.-2inf

十月初 LCA 营里说有 CCPC 名额，于是跟 Iceturky 和 Pigsyy 组队，队名是 "O(甜甜圈)!"。后来想把阶乘号放在括号里，但好像不好改了，遂放弃。

Day.-14（11.1）

我在 CSP 爆炸了。

但是之前准备在 LCA 营开课前的三天间隙 VP，所以先尽可能调整了一下状态。

之后三天各开了一场，分别是 2023.2022Nanjing 和 2024Jinan，三人一机 VP 出了两场下位金和一场上位银。打 2023Nanjing 的时候最后我在调 K，未能调出，赛后五分钟发现变量名写错调出来了，有伏笔。

感觉如果没有 VP 的话，我可能会在失败的阴影中学不下去摆若干天，这倒也帮我调整心态了。

Day.0（11.15）

早上出发，打了一路杀戮尖塔，故障机器人太牛了。

在酒店外卖了麦，吃到一半想起来赛时会提供麦，不管了。

下午开幕式，面到了 waauto 和 zyd 学长，交换了徽章。有合照但是懒得放了。

然后热身赛，怎么 OJ 一直在爆，最后零题愤然离场。

晚上有 OIER 大聚餐，爽吃，有合照但是懒得放了。然后跟本地人林哥去 KTV 唱了俩小时，林哥唱功还是太权威了。

茫茫冻土身相随，有心炽如火

你方唱罢我登场，思维见真知

Day.1（11.16）

早上从酒店出发得晚了点，于是骑共享单车去的。

然后就开始了，syy 过了签到 C 去看 E 了。然后我被 F 骗出来一个斜率优化，写完才意识到假了，于是 wjr 上机开始鏖战 K 的大分讨，我接着想 F。

之后 syy 一眼把 E 秒了，把思路传给我之后去看 L 了。这个 E 看起来不太好写啊。wjr 被 K 卡住的时候我就上去写了一点，最后只写完了预处理。然后 syy 上机写 L，好像细节也不少，吃了两发后过了。

然后我写 F，写完 WA 了，结果手造样例把自己卡了？修了就过了。开始狂写 E，写到一半 wjr 来把 A 过了，然后接着写，然后 RE 了，然后 WA 了。最后也未能调出，赛后一分钟发现写错了一个数调出来了，伏笔回收。唐完了，$5$ 题遗憾离场。

然后在场里随机游走，似乎不少熟人都是 $5$ 题，怎么都坠机了。见到了哥哥并进行了合照，不过也懒得放了。

然后滚榜，念滚榜的人很有激情，好评，但光速念完“noip200 分被别走散抓摆之后不会梦到 noi 笔试少 1 分退学组一辈子乐队”还是有点难绷。

拿到了中位银牌，同时发现 6 题少罚时才能金，这下感觉也没那么遗憾了。

然后去山大食堂吃晚饭，并且买东西把餐券花完了，爽。

XCPC 赛制还挺有意思的，有机会还想打。下次机会可能是 THUPC？希望那个时候还没退役吧。

所为所作消散人世，所思所忧归向虚空

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-12 00:27:33

11.05 优化 - 构造

• 贪心

调整法，若调整规则使方案 $S$ 不变劣，则只有无法调整的方案可能是最优解。

对于集合 $S$ 上的二元关系 $\lt$，若满足非自反性、反对称性、传递性、不可比性的传递性则称其满足严格弱序。若元素满足弱序关系，可以使用邻项交换，且最优解中任意交换两个相邻元素都不会变优。

模拟费用流（反悔贪心）。

• 构造（Ad-Hoc）

组合模式（注意力）。

CF632C The Smallest String Concatenation

题意

给定 $n$ 个字符串 $s_i$，总长为 $m$，任意重排后最小化新串字典序。$m\le 5\times 10^4$。

题解

对于一个答案排列 $p$，若存在相邻元素满足 $s_{p_{i+1}}s_{p_{i}}\lt s_{p_i}s_{p_{i+1}}$，将这两项交换一定不劣。于是最终排列任意相邻元素均满足 $s_{p_{i}}s_{p_{i+1}}\le s_{p_{i+1}}s_{p_{i}}$。如果可以找出一种权值 $f(S)$ 满足弱序关系，且 $f(s_{p_i})\le f(s_{p_{i+1}})$ 与 $s_{p_{i}}s_{p_{i+1}}\le s_{p_{i+1}}s_{p_{i}}$ 等价，则可以说明最优解唯一。

考虑比较 $ab,ba$ 的 $a,b$ 两串，通过复制若干份可得 $a^{\left|b\right|},b^{\left|a\right|}$ 两个等长的串。由于若干 $a,b$ 任意拼接得到的最优串一定是 $a$ 在前 $b$ 在后，于是 $ab\le ba$ 可以表示为 $a^{\left|b\right|}b^{\left|a\right|}\le b^{\left|a\right|}a^{\left|b\right|}$。由于长度相同，这相当于比较 $a^{\left|b\right|},b^{\left|a\right|}$。于是令 $f(S)$ 表示 $S$ 无限复制得到的串，以字符串为权值即可。这样就证明了排序做是对的。

然而排序时若暴力比较，单次复杂度是 $\mathcal O(\left|a\right|+\left|b\right|)$，可能有 $\mathcal O(nm)$ 的最劣复杂度，比较爆炸。考虑优化比较，令 $a$ 为较短的串，先暴力比较 $a,b$ 前 $\left|a\right|$ 位，若全相同会对 $b$ 和其后缀比较，可以用 Z 函数预处理实现 $\mathcal O(1)$ 查询。还相同的话是一个后缀与 $a$ 比较，可以直接暴力。于是做到了单次 $\mathcal O(\min(\left|a\right|,\left|b\right|))$ 的比较。

考虑使用归并排序，并分析其复杂度。总共有 $\mathcal O(\log n)$ 层，每层放入排序结果的总串长为 $m$。同时排序中若产生 $\mathcal O(len)$ 的比较复杂度，会将长度至少为 $len$ 的串放入排序结果，于是总复杂度也是 $\mathcal O(m\log n)$ 的。

还有线性做法，据说是 Trie 树上的奇技淫巧，不管了。

典题

题意

给定 $n$ 个二元组 $(t,w)$，任意重排为 $p$，最小化 $\sum w_{p_i}(\sum_{j\lt i}t_{p_j})$。

考虑相邻的 $(t_1,w_1),(t_2,w_2)$，这样排序较优需要满足 $t_1w_2\le t_2w_1$，两边除以 $w_1w_2$ 可得 $\frac {t_1}{w_1}\le \frac {t_2}{w_2}$，也即 $\frac tw$ 从小到大排序最优。以下令 $f=\frac tw$。

Ex 题意

给定 $k$ 个二元组 $(t,w)$ 序列，要求每组内先后顺序不能改变，合并成一个序列，仍然最小化该式。

考虑同一个序列中相邻两项，若 $f_i\ge f_{i+1}$ 则填完 $i$ 后一定接着填 $i+1$，证明可以考虑最终序列中若这两项之间有元素，对其 $t,w$ 均求和后求 $f'$ 值。若 $f_i\ge f'$ 则可以提到 $i$ 之前，若 $f'\ge f_{i+1}$ 则可以放到 $i+1$ 之后。由于 $f_i\ge f_{i+1}$，两个条件至少有一个成立，于是一定能调整到 $i,i+1$ 相邻。

之后通过这样的邻项合并可得若干 $f$ 不降的序列，之后贪心取当前 $f$ 最小的可取元素即可。

Ex Ex 题意

$n$ 个点的树，每个点有一个二元组 $(t,w)$，序列中要求父亲在儿子前面，仍然最小化该式。UVA1205 和 ABC376G 大概是 $t=1$ 的版本。

每次找非根节点中权值最小的，若其父亲被填入序列，则必然将该点立刻填入序列。于是将其与父亲合并，产生 $t_{f}w_u$ 的代价，得到一个 $(t_u+t_f,w_u+w_f)$ 的新点。此时父亲的权值变小了，可以用堆维护这个过程，复杂度 $\mathcal O(n\log n)$。

HDU6326 Problem H. Monster Hunter

题意

给定一棵树，除根节点 $1$ 外每个点上有一个怪物，需要消耗 $a_i$ 生命清除，之后可以获得 $b_i$ 生命。走到一个点前需要清除其父亲节点上的怪物，求要清除所有怪物需要的最小初始生命。多组数据，$\sum n\le 10^6,1\le a_i,b_i\le 10^9$。

题解

考虑没有树的限制，可以任意排序时怎么做。对于相邻两项 $(a_i,b_i),(a_j,b_j)$，此时贡献为 $\max(a_i,a_j+a_i-b_i)$，若交换则贡献为 $\max(a_j,a_i+a_j-b_j)$，要最小化贡献。以 $\max (a_i,a_j)$ 为基准，若 $a_i-b_i,a_j-b_j$ 不同号容易比较，一定是 $a_i\le b_i$ 的排在前面，这也是容易感性理解的。

讨论同号情况，若均满足 $a\le b$，则是将 $a_i,a_j$ 之一减小后取最大值。显然只有减小初始最大值有效，于是一定会把初始最大值放在后面，即按照 $a$ 从小到大排序。若均满足 $a\gt b$，有 $a_i\lt a_{i}+a_j-b_j,a_j+a_i-b_i\gt a_h$。将原式简写成 $\max(A,B),\max(C,D)$ 后有 $A\lt D,B\gt C$，手推一下就会发现原式比较大小与 $B,D$ 比较大小是等价的。于是变为比较 $a_j+a_i-b_i,a_i+a_j-b_j$ 的大小，得到按 $b$ 从大到小排序最优。

综上，前面 $a\le b$ 部分按 $a$ 升序排序，后面 $a\gt b$ 部分按 $b$ 降序排序，容易发现这样的大小关系具有传递性等性质，也可以编出一个权值 $f(a,b)$ 并以此排序。上树之后考虑邻项合并，即找到当前非根节点中权值最优的点，将其与父亲合并。用堆和并查集维护即可，复杂度 $\mathcal O(n\log n)$。

CF865D Buy Low Sell High

题意

给出每天的价格，每天可买入一次或卖出一次，也可以什么都不做，最大化净收益。$n\le 3\times 10^5$。

题解

考虑依次决策每天的行动，可以在这天买入，之后某天卖出；或者找之前价格最低的一天买入，在当天卖出。使用堆维护此前没用过的价格，若最小值比 $a_i$ 小则可以匹配。然而这样贪心是错误的，原因是最优解中可能跳过中间的元素进行匹配。

考虑支持反悔操作，对于前面选择过的 $(i,j)$ 配对，需要支持将其改成 $(i,k)$，其中 $i\lt j\lt k$。注意到此时收益会增加 $a_k-a_j$，于是对于每个 $(i,j)$ 均在堆中额外加入一个 $a_j$ 作为代价即可，当然每天仍需加入一个 $a_i$ 表示直接在这天买入。由于 $j$ 在反悔后实际上不被操作，两个均取是没有问题的。复杂度 $\mathcal O(n\log n)$。

QOJ9222 Price Combo

11.07 构造

CF862C Mahmoud and Ehab and the xor

题意

给定 $n,x$，构造 $n$ 个不超过 $10^6$ 且两两不同的非负整数使得异或和恰为 $x$。$n,x\le 10^5$。

题解

只有 $n=2,x=0$ 无解，先判掉就行。

• 增量

考虑构造若干个异或和为 $0$ 的元素，比如 $1,2,3$，以及任意 $4t,4t+1,4t+2,4t+3$，之后按照对 $4$ 取模的结果分讨一下，用不超过 $4$ 个数凑出 $x$，再拼上若干个大小为 $4$ 的组即可。

• 随机 + 微调

考虑随机出 $(n-1)$ 个数，此时其异或和 $S$ 大概是均匀随机的，判断最后一个数 $S\oplus x$ 是否出现过即可。由于可选值域比 $n$ 大不少，合法概率较高，期望线性次就能取到一组解。

去随机的话，随机或直接填 $(n-2)$ 个数，之后后两个数 $i\oplus j\oplus S=x$，这会形成若干个数对。由于值域足够大，根据抽屉原理一定存在合法的数对。只需要特判一下 $x=0$ 的情况即可。

• 组合模式

这题好像没咋体现啊，不过构造题主要是这三种做法。

CF468B Two Sets

分析一下发现是必须在同一个集合内。

P3588 [POI 2015 R2] 沙漠 Desert

优化建图，差分约束。

差分约束同时最优化所有非定点的值。

子问题：分治、倍增、递归、增量、差分、迭代、微调。

11.09 优化

• 匹配

点覆盖：用点集覆盖所有边。

独立集：没有公共边的点集。

两者互为补集，即任意一个点覆盖的补集一定是合法独立集，反之亦然。

Konig 定理：二分图中，最小点覆盖中的顶点数量等于最大匹配中的边数量。

二分图最大权匹配：补上 $0$ 边可转化为最大权完美匹配。

顶标：给每个点一个标号，满足边权不大于两端标号和。

这样匹配权值一定不超过标号总和，于是找到一组标号和一个匹配权值相等，即为最大匹配权值和。

需要相等边组成的子图存在完美匹配，仍然考虑增广过程。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-10 14:51:30

这个 DP 的样式非常奇诡。——LCA

LCA 模拟赛题，太困难了。基本是复述 LCA 给的题解。

题意

给出一个森林，点有点权 $a_u$，边有边权 $b_u$。标记一个点需要花费 $a_u$ 的代价，若其父亲已被标记，也可以花费 $b_u$ 的代价。标记随时可清除，且不能同时存在超过 $k$ 个标记点。要求树上的 $m$ 个点均被标记过，求最小代价。多组数据，$T\le 30,m\le n\le 5000,k\le 5$。原题。

弱化版：每个点只能被标记一次，$T\le 5,m\le n\le 10^5,k\le 10$。

题解

判掉 $k=1$，此时答案为 $\sum a$；将 $b_i$ 对 $a_i$ 取 $\min$，同时以 $0$ 为树根且不标记，避免讨论。考虑标记点形态，$k=2$ 时标记 $u$ 点后可向下拓展到子节点，但是需要清除 $u$ 点标记才能接着向下，最终能覆盖毛毛虫形状内的点。定义单点是 $1$ 合法的，对于 $i\gt 1$，定义 $u$ 子树 $i$ 合法当且仅当存在一个儿子 $i$ 合法， 且其他儿子均 $(i-1)$ 合法，这也能解释 $2$ 合法的形状。

于是对于弱化版，设 $f_{u,i}$ 表示 $u$ 子树内关键点均被标记过，且从 $u$ 开始的拓展过程 $i$ 合法的最小代价。状态不考虑 $u$ 点代价，因为其取值受父亲影响。另外令 $f_{u,0}$ 表示 $u$ 不选时的最小代价。转移为 $f_{u,1}=f_{u,0}=\sum\min(f_{v,k}+a_v,f_{v,0})$，对于 $i\gt 1$，有 $f_{u,i}=\min(f_{v,i}+b_v+\sum_{t\ne v}\min(f_{t,i-1}+b_t,f_{t,k}+a_t,f_{t,0}))$，只需先对第二个式子求和，再找最优差值更新即可。最后若 $u$ 必须被标记，将 $f_{u,0}$ 赋为正无穷，复杂度 $\mathcal O(nk)$。

对于原题，同一个点可被学习多次，即可以从 $u$ 拓展到 $v$，在 $v$ 拓展的过程中扔掉 $u$，之后需要标记 $v$ 或其他子节点时再把 $u$ 标记回来。据此设 $f_{u,i,j}$ 表示考虑 $u$ 子树，用到了至多 $i$ 的空间，过程中 $u$ 的子节点拓展需要 $u$ 点标记 $j$ 次的最小花费。与上面相同，状态不考虑 $u$ 点代价，这会在父亲节点上决策。

这个状态在定义什么？其包含子树内其他点的标记次数和方式，记录过程中的最大空间消耗和 $u$ 用于拓展的标记次数，以便向上转移。由于空间越大越可操作，$f_{u,i,j}$ 随 $i$ 增大单调不增。另外 $f_{u,i,0}$ 并非不标记 $u$，而是已经考虑的过程没有用 $u$ 拓展，还没有因此标记过 $u$。最终 $f_{u,i,0}$ 的值是无意义的，事实上代表的是 $i'\lt i$ 的 $f_{u,i',y}$，该状态也不能转移给父亲。至于真的不标记，再设 $g_u$ 表示 $u$ 不用于拓展时子树内最小代价，此时子树内其他拓展过程均可使用 $k$ 的空间，不用记录。

由于从某点开始同时向多个子树拓展不优，可以依次处理每个子树，这样可用空间更大。于是可依次将每个子树 $v$ 的信息拼到 $u$ 上。具体地，新拼上一个子树 $v$ 时，有以下几种转移（$t_v$ 表示 $v$ 是否需要标记；均有限制 $i\ge 2,j\ge 0,y\ge 1$）：

1. $v$ 从 $u$ 拓展来，且拓展过程中一直保留 $u$，$v$ 标记 $y$ 次：$f_{u,i,j}+f_{v,i-1,y}+yb_v\rightarrow f'_{u,i,j}$。
2. $v$ 从 $u$ 拓展来，且 $v$ 不用于向下拓展：$f_{u,i,j}+g_v+t_vb_v\rightarrow f'_{u,i,j}$。
3. $v$ 部分从 $u$ 拓展来，过程中扔掉 $u$，$v$ 标记 $y$ 次，其中 $x$ 次从 $u$ 拓展：$f_{u,i,j}+f_{v,i,y}+xb_v+(y-x)a_v\rightarrow f'_{u,i,j+x}$，有限制 $0\le x\le y$。
4. $v$ 不从 $u$ 拓展，标记 $y$ 次：$f_{u,i,j}+f_{v,k,y}+ya_v\rightarrow f'_{u,i,j}$；$v$ 不标记代价为 $g_v+t_va_v$，不如 2 优。
5. $u$ 不向下拓展，$v$ 标记 $y$ 次：$g_u+f_{v,k,y}+ya_v\rightarrow g'_u$；$v$ 不标记：$g_u+g_v+t_va_v\rightarrow g'_u$。

最难理解的可能是转移 3，即 $v$ 用了全部的 $i$ 空间，此时每次从 $u$ 拓展都要重新标记 $u$。这里状态第三维记录的是用于拓展的标记次数，理解了这一转移大概就能理解状态设计的方式了。

至于初始值，开始的时候只有单点 $u$，所有值均为 $0$。$f_{u,1}$ 没有转移，注意到此时 $u$ 同样不能向下拓展，全部赋成 $g_u$ 即可。暴力实现的话，转移 2.4.5 的复杂度不超过 $\mathcal O(n^2k)$，可以接受；而转移 1 是 $\mathcal O(n^3k)$ 的，转移 3 不限制上下界是 $\mathcal O(n^4k)$ 的，均需优化。

对于转移 1，注意到是对所有 $y$ 取最小值，于是设 $h_{i}=\min(f_{v,i,y}+yb_v)$，转移就变成了 $f_{u,i,j}+h_{i-1}\rightarrow f'_{u,i,j}$。这样转移和 $h$ 的预处理都是 $\mathcal O(n^2k)$ 的了，可以接受。

对于转移 3，注意到下标变化只与 $x$ 有关，先用同样方法避免掉 $y$ 的枚举。具体地，对于确定的 $i,j,x$，会用 $y\ge x$ 的 $f_{v,i,y}+xb_v+(y-x)a_v$ 转移。将 $y$ 分离出来得到 $f_{v,i,y}+ya_v$，预处理其后缀最大值 $h_{i,y}$ 即可，复杂度同样是 $\mathcal O(n^2k)$ 的。之后转移为 $f_{u,i,j}+h_{i,y}+x(b_v-a_v)\rightarrow f'_{u,i,j+x}$。注意到 $j$ 一维显然不会超过子树大小，可以套用树形背包，复杂度就是 $\mathcal O(n^2k)$ 的了。

于是做到了 $\mathcal O(n^2k)$ 的时空复杂度， 单组数据就能过了。然而原题是 $30$ 组多测，根本不是人。不过还有常数优化！考虑一次 $i$ 合法的拓展，若新覆盖的点数少于 $i$，则其一定也是 $(i-1)$ 合法的，可以将其拼到某次 $i$ 合法的拓展上。因此一次 $i$ 合法的拓展至少新覆盖 $i$ 个点，于是 $f_{u,i,j}$ 的 $j$ 一维可限制 $j\le \lceil\frac {s_u} i\rceil$。加上这个常数大大减小，可以通过。

代码

见云剪切板。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-02 12:46:29

悟已往之不谏，托遗响于悲风。

省流：打得烂完了，去不了 WC。

主要记录考场经过和反思，给自己留下点教训，作为游记可能没那么友好。

Day.-2（10.29）

从初赛到这天一直在 LCA 长训营，感觉学到了不少东西啊。

下午放假前有出征仪式，还有经典切蛋糕，感觉不错。

Day.0（10.31）

上午来学校打板子，中午出发，车上一起听睡觉，到了之后打板子。

晚上试机，面到了不少人。还有哥群合照环节，不过要拍的时候灯突然灭了，最难绷。

回酒店喝蜜雪，一块玩了一会，睡觉。

Day.1（11.1）

上午打板子。下午进考场，开题。

• 14:30 - 14:50 读了所有题面。感觉 T1 能反悔贪心，但应该不会这么难，于是又想了一会发现只有一个限制会爆，再调整就行，迅速过掉。
• 14:50 - 16:00 在做 T2。想了一会只会 $\mathcal O(m\log m+2^knk(\lpha(n)+\log k))$，又想了一会感觉比较难优化，于是直接写了。
• 16:00 决定扔掉只会波动 $20$ 分的 T2，并准备同时开后两个题。
• 16:00 - 16:30 对 T3 胡出来一个 $\mathcal O(qL_1+L_2)$ 的神秘做法，需要哈希和 KMP，能过 $50$。由于开场读到 T4 可做，没写代码而是先去想 T4 了。
• 16:30 - 17:00 对 T4 把特殊性质都胡出来了，感觉有 $56$。事实上这部分假完了，但我不知道。
• 17:00 感觉必须开始写了，经过抉择选了感觉好写的 T4。
• 17:00 - 17:45 写了 T4 的两个性质，但都过不了样例，试图调到 17:45 才发现漏了限制。思考一会后发现 $36$ 分还能修，而且这个东西 SDSC 讲过。
• 17:45 - 18:05 修了一段时间，但可能是心态波动的原因，没有调出所想的东西。
• 18:05 已经开始慌了，又用混乱的大脑在后两题之间权衡了一下，感觉剩下的时间已经调不出带哈希的 T3 了，于是接着调 T4。
• 18:05 - 18:30 一直在调 T4，过程中调不出 $36$ 急了，于是重写好写点的 $20$，然而一直过不了样例 2，调到最后也没调出。

大概就是这样爆炸的，后两题没分，T2 可能只有 $80$。出场后有种恍惚感，不知道咋回到大巴上的。然后吃了点东西，昏睡了会。最后回到了放大周空无一人的学校宿舍，很快就睡了。

Day.2（11.2）

意料之外地没有失眠，可能是确实比较累，也可能是已经接受这个结果了。八点半起床之后就来机房写游记，毕竟虽然惨败，还是要认真面对的。

先不倒下，然后出发。

很不幸地，这是我发挥最差的一场比赛，可能即使算上模拟赛也是；但很幸运地，这没发生在影响进队的 NOIP，而发生在只影响到 WC 的 CSP，已经是不幸中的万幸了。此前确实没有在 OI 赛制正式赛大失误的经历，NOIP 前能有这样一场教训，感觉也不一定是坏事吧。

复盘这场的话，有一些决策出现了问题：

• 如果在想出 T3 做法时直接开写，在心态仍然稳定的情况下应该可以调出，不会影响到 T4。
• 如果在写 T4 前检查正确性，或开写前先写暴力验证，就不会浪费太多时间，最终也会有一些暴力分。
• 如果发现失误后能稳住心态，冷静调试，结果可能会略好一点。

但是没有如果，打烂的事实已经无法挽回了。问题主要来源于没有认清自己的水平，或许是模拟赛让我感觉自己能拿高分，于是比较激进地同时开了两题，最后被 T4 卡死。事实证明水平不足的情况下，之前那种会一点写一点的策略才是最稳定的，之后模拟还得调整下。

另外场内心态还是不够稳定，还得锻炼。至于场外心态，感觉自己也没有特别沮丧吧，现在已经大概调整过来了。加练，NOIP 再战。

祈祷

假装丟掉 昨日可悲真相

再跌宕 自顾自地 逆着风的浪潮

寻求着月光 为此也迷茫

还是要走到 生命最后终章

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-28 08:18:47

10.22 数据结构

• 颜色段均摊

CF444C DZY Loves Colors

题意

有长为 $n$ 的序列 $a,b$，初始 $a_i=i,b_i=0$。操作对一个区间 $[l,r]$ 内的 $i$ 进行 $b_i\leftarrow b_i+\left|a_i-k\right|,a_i\leftarrow k$ 的修改，查询 $b$ 的区间和。$n,m\le 10^5,k\le 10^8$。

题解

由于 $a$ 有不同，对 $a$ 覆盖时 $b$ 的变化量不同，难以直接维护。然而区间覆盖是破坏性操作，会使得这段区间之后一直相同，可以使用势能线段树或颜色段均摊解决，前者即只对线段树上颜色相同的节点操作。

至于颜色段均摊，考虑维护 $a$ 序列所有极长连续相等段，每次只对整段操作，显然原来相等的 $a$ 得到的贡献相等，可以区间加解决。之后把 $[l,r]$ 变成新的一段。若有 $k$ 个段被完全包含，则会进行 $(k+2)$ 次区间加，且段数减少 $(k-1)$，于是区间加的总次数不超过 $3n+q$。使用线段树或树状数组维护区间加区间求和即可，复杂度 $\mathcal O((n+q)\log n)$。

CF1638E Colorful Operations

区间赋值操作启发我们使用 ODT。对于每种颜色再维护一个标记，元素被改变颜色时处理一下标记贡献的改变即可，大概是区间加单点求值，上树状数组就行。之后应该会写。

CF453E Little Pony and Lord Tirek

题意

每个位置有初始值 $s_i$，上界 $m_i$，单位时间的增加量 $v_i$。进行 $q$ 次操作，在经过一段时间后求区间 $[l,r]$ 内所有值的和并将其清空。$n,q\le 10^5$。

题解

若上次清空到求值经过了 $t$ 单位时间，当前值为 $\min(m_i,tv_i)$，分讨 $\lfloor\frac{m_i}{v_i}\rfloor$ 和 $t$ 的大小关系即可。注意到贡献只跟 $t$ 有关，于是考虑按上次清空时间进行颜色段均摊，这样每段内的 $t$ 相等，容易计算贡献。这样变成若干段区间的 $\min(m_i,tv_i)$ 之和，根据 $\lfloor\frac {m_i}{v_i}\rfloor$ 离线扫描线即可解决，复杂度 $\mathcal O((n+m)\log n)$。

P5066 [Ynoi Easy Round 2014] 人人本着正义之名

可以发现向前后位运算本质是一些连续的连续段内某一种段长度增长，另一种长度减短，使用平衡树维护所有连续段并打标记即可。为了防止段缩没，还需要记录区间内最短的两种区间长度，当出现长为 $0$ 的段时暴力找到并合并左右两段。太难写了还卡常，遂弃之。

LOJ6777「2021 营员交流」大毒瘤

可以维护火段和非火段，也是特别难写，还有分块做法。反正弃了。

• 扫描线

UOJ637【美团杯2021】A. 数据结构

题意

给定序列 $a$，$q$ 次询问给出 $[l,r]$，求将 $[l,r]$ 内的数增加 $1$ 后整个序列的数字种类数。$n,q\le 10^6,a_i\le n$。

题解

首先不存在某数比存在某数好处理，这是因为存在时出现次数不确定，然而不存在就是出现次数为 $0$，于是用 $n-1$ 减去不存在的个数即为答案。之后考虑拆贡献，即对每个 $x$ 考虑选择哪些区间 $[l,r]$ 会导致不存在 $x$。

注意到这需要选的区间包含原序列的所有 $x$，且不能包含 $x-1$。前一个限制是二维平面上一个矩形，后一个限制是若干不交的矩形，且所有 $x$ 对应的矩形数量总和是 $\mathcal O(n)$ 的。于是枚举后一个限制的矩形并与前一个矩形取交，再进行矩形加单点查即可，扫描线 + 树状数组即可维护，复杂度 $\mathcal O((n+q)\log n)$。

牛客挑战赛某题

题意

给定三个序列 $a,b,c$，求所有 $l\le r$ 在三个序列上区间极差的乘积之和。$n\le 3\times 10^5$。

题解

直接扫，同时维护所有子集区间和即可实现某个序列的区间加，然后单调栈维护一下就行。没题写不了。

lxl 还说，线段树复杂度要分定位和计算两部分，一般来说定位部分比较慢，所以信息多一些对常数的影响不大，只要把信息压结构体里避免重复定位就行。

P11390 [COCI 2024/2025 #1] 教师 / Učiteljica

每个区间内 $k$ 种出现次数的存在性会形成 $2^k$ 种状态，通过容斥转化为求 $S$ 内的次数均不存在的区间数，之后再取补集变成存在至少一个 $S$ 内的次数的区间数，这个就可以直接矩形面积并求了，复杂度 $\mathcal O(2^kkn\log n)$。当然后半部分也可以不取补集，而是记录 $f_i$ 表示 $S$ 中存在的个数，然后扫描线求全局 $0$ 的数量，复杂度是相同的。之后应该会写。

某典题

题意

给出 $n$ 个区间 $[l_i,r_i]$，$q$ 次询问编号在 $[L,R]$ 内区间并的大小。$n,q\le 10^6$。

题解

扫描 $R$ 这一维，维护 $f_i$ 表示当前覆盖 $i$ 位置的区间最大编号，询问 $f_i\ge L$ 的 $i$ 个数（离散化后为权值和）。$f$ 的修改是区间覆盖，于是直接上 ODT，再开一棵线段树 / 树状数组维护每个 $L$ 的答案即可，复杂度 $\mathcal O((n+q)\log n)$，没题写不了。

10.24 扫描线

多标记问题：

先合并相邻同种标记，尝试交换相邻标记 / 去除无用标记，再考虑标记之间的合并以及信息与标记的合并，以此设计标记。

P3246 [HNOI2016] 序列

题意

给出序列 $a$，$q$ 次询问区间 $[L,R]$ 内所有子区间 $[l,r]$ 的最小值之和。$n,q\le 10^5$。

题解

考虑对 $R$ 扫描线，设 $f_i$ 表示当前 $[i,R]$ 的最小值，所求为 $[L,R]$ 区间内 $f_i$ 的历史和。首先 $R$ 移动时可以使用单调栈维护最小值的变化，需要做 $\mathcal O(n)$ 次区间加。之后需要求区间历史和，用任意一种方式维护就行，复杂度 $\mathcal O((n+q)\log n)$。由于 lxl 刚讲了推标记的方法，写了这个。

P8868 [NOIP2022] 比赛

是上题的双序列版本，lxl 说这种题只需要维护 $a,b,ab$ 的和就能做，之后应该会写。

CF997E Good Subsegments

题意

给出排列 $a$，$q$ 次询问区间 $[L,R]$ 内有多少个子区间 $[l,r]$ 为区间连续段，连续段定义为其在值域上连续，即 $\max-\min =r-l$。$n,q\le 1.2\times 10^5$。

题解

考虑求全局区间连续段数的做法，通过维护 $\max-\min-r+l$ 这个非负值并求最小值 $0$ 的个数求解。同样放到这题，扫描右端点 $R$，设 $f_i$ 表示 $[i,R]$ 区间的权值，其变化也可以用单调栈表示成 $\mathcal O(n)$ 次区间加。现在要求的是 $f$ 区间历史最值及个数。

使用线段树，设计标记时考虑历史最值累加和加标记的关系，发现不可能出现加标记两侧都是历史标记的情况，否则存在一个历史标记没有用。于是标记为 $(l,c,r)$，表示先加 $l$，再累加 $c$ 次历史最值，再加 $r$。信息就维护当前和历史最值及个数，合并推一推就出来了。总复杂度 $\mathcal O((n+q\log n))$。听说 CF 题解是分块？怪不得开这么小。

P9990 [Ynoi Easy Round 2023] TEST_90

跟上两题差不多推历史和标记就行，之后应该会写。

P3863 序列

题意

给定长为 $n$ 的序列，$q$ 次操作，区间加或查询某个位置在过去的多少秒内不小于 $y$。$n,q\le 10^5$。

题解

由于是区间修改和单点查询历史信息，考虑换维扫描线，扫序列维，维护当前每个时刻对应的值。于是问题转化为在长为 $q$ 的序列上后缀加，求前缀中不小于 $y$ 的个数。使用分块维护，每个块内对所有数排序，修改时给整块打标记，暴力重构散块，复杂度 $\mathcal O(\frac qB+B\log B)$；查询时整块内二分，散块内暴力查，复杂度 $\mathcal O(\frac {q\log B}B+B)$，取 $B=\sqrt q$ 可得最优复杂度 $\mathcal O(q\sqrt q\log q)$。

事实上排序时只有一个后缀加了值，可以分成两半进行归并，这样修改的复杂度就是 $\mathcal O(\frac qB+B)$ 了，平衡平衡可以把 $\log q$ 也放根号里，跑得快了一些。

P7560 [JOISC 2021] フードコート (Day1)

题意

有 $n$ 个队列，每个事件可能向编号在 $[l,r]$ 内的队尾加入 $k$ 个 $c$，或删掉队头的至多 $k$ 个元素直到删空，过程中询问当前某个队列中第 $t$ 个元素。$n,q\le 2.5\times 10^5,k\le 10^9,t\le 10^{15}$。

题解

由于每个队列是独立的，修改影响一个区间内的队列，且询问只在单个队列内，考虑换维扫描线，扫描序列维，数据结构维护操作维。这样每个修改只会加入和删除各一次，查询时只考虑操作维的一段前缀即可。

于是操作序列上有一些加入和删除操作，查询进行前缀操作后第 $t$ 个元素。在序列不会删空时是容易做的，只需要线段树二分出所有加入操作的第 $(t+s)$ 小位置即可。可能删空时考虑找到最后一次删空的时刻，从这个位置开始往后做。不难发现这个位置是该前缀内前缀和最小值，于是线段树维护区间和、区间负数的和以及前缀和最小值及位置即可解决，复杂度 $\mathcal O(q\log q)$。

P11536 [NOISG 2023 Finals] Curtains

题意

给出 $m$ 个区间 $[s,e]$，$q$ 次询问一个区间 $[l,r]$ 能否被表示为若干给定区间的交。$n,m,q\le 5\times 10^5$。

题解

选上所有 $l\le s\le e\le r$ 的区间 $[s,e]$ 一定不劣，判断这些区间能否完全覆盖 $[l,r]$ 即可。考虑扫描 $r$ 这一维，对每个点 $i$ 维护 $f_i$ 表示 $s\le i\le e\le r$ 的区间中 $s$ 的最大值。若 $[l,r]$ 内的 $f$ 值均不低于 $l$，则每个点都能被 $[l,r]$ 内的区间覆盖，否则一定不合法。于是进行区间取最大值，求区间最小值即可，这个可以线段树 $\mathcal O((n+q)\log n)$ 维护。

还有一些别的做法，大概是维护一些奇妙的可合并标记，感觉都没有这种做法好啊，也忘了当时咋做的了，不管了。

10.26 树上问题

• 路径修改，查询树上邻居。考虑对每个点维护其所有轻儿子的信息，修改量可以控制到 $\mathcal O(\log n)$。

P5314 [Ynoi2011] ODT

题意

给定一棵树，需要支持路径加，求一个点及其邻居中第 $k$ 小点权。$n,m\le 10^6$。

题解

如上述，对每个点用数据结构维护其所有轻儿子的点权，路径修改会影响到 $\mathcal O(\log n)$ 条轻边对应点的数据结构。同时维护每个点的点权，查询时将其父亲和重儿子加入数据结构查询即可，查完再删去，即可做到 $\mathcal O(q\log ^2 n)$ 的复杂度。这个需要卡常，不写了。更低复杂度是极难的，不管了。

不行，太牛了，之后应该会写。

P8511 [Ynoi Easy Round 2021] TEST_68

题意

给定一棵树，点有点权，对每个点求其子树外两点点权异或和的最大值。$n\le 5\times 10^5,a_i\le 10^{18}$。

题解

性质题。考虑找到全局最大异或和 $a_x\oplus a_y$，则对于所有 $x,y$ 均在子树外的点 $u$ 均已确定答案，未确定的只有 $x,y$ 两点到根路径上的点。对于这两条路径，其上点子树外的范围从根到底逐渐扩大，可以从根到底依次加入数并实时维护最大异或和。扔到 Trie 树上求一下就好了，时空复杂度 $\mathcal O(n\log V)$。

• 树上两条不相交路径，可以枚举点然后分到子树内外。

P6072 『MdOI R1』Path

题意

给定一棵树，边有边权，选择两条点不相交的路径使得路径边权异或和之和最大。$n\le 3\times 10^4,w\le 10^9$。

题解

如上，考虑枚举分界点分到子树内外，之后需要分别求子树内外最大路径异或和。首先路径异或和可以用 $d_x\oplus d_y$ 来表示，其中 $d_i$ 为点到根的路径异或和。于是子树外的信息即上题所求，可以 $\mathcal O(n\log V)$ 解决；子树内比较暴力的方式是启发式合并，可以做到 $\mathcal O(n\log n\log V)$。

考虑进一步优化，再次考虑上题中 $d_x\oplus d_y$ 最大的点对 $(x,y)$，注意到两条路径外所有点的 $f_u$ 均相同，此时这些点中存在互相包含关系，于是只有极大的子树可能贡献到答案。显然这些子树两两不交，可以直接暴力 $\mathcal O(n\log V)$ 解决。至于路径上的点，从底到根子树依次扩大，按此顺序依次加入即可，总时间复杂度也是 $\mathcal O(n\log V)$ 的。

CF1344E Train Tracks

可以根据树上启发式合并证明限制区间总共只有 $\mathcal O(m\log n)$ 个，通过启发式合并等找出这些区间后贪心即可。之后应该会写。

• 求一个点最终走到哪个点，可以尝试判断 $(x,y)$ 是否可达，之后通过树剖 / 二分之类的方式求出终点。

未公开题目

题意

给定一棵二叉树，每个点上有形如 $y\le a$ 或 $y\ge a$ 的限制，$y$ 值若满足限制则走到左子树，否则走到右子树。要求支持单点修改，查询 $y$ 值从 $x$ 点开始走会停到哪个叶子。

题解

先树剖，之后对于每条重链，用线段树维护 $y$ 要走完某个区间需满足的上下界。走的时候二分一下在当前重链能走到哪，之后跳出去即可，复杂度 $\mathcal O(q\log ^2 n)$。没题写不了。

神秘来源题目

题意

给定一棵树，每条边有一个字符，询问给出起点 $x$ 和字符串 $S$，每次走向邻边中在 $S$ 中最靠前的边并将该边删除，求最终停的点。$n,q\le 3\times 10^5,\sum=26$。

题解

与上题相同，然而这里走一条路径的要求变成若干 $i$ 在 $j$ 前的限制或起来，共 $\sum^2$ 个。这是 01 信息，直接压位存储。然后先向上跳到跳不动，之后再沿着重链跳，跳出重链时可以暴力求下一条重链，复杂度 $\mathcal O(q\log ^2n \frac {\sum^2}{w})$。lxl 说如果度数太大需要用数据结构维护轻边，不过这题不用。没题写不了。

P8990 [北大集训 2021] 小明的树

把合法转化为灭的灯为连通块，之后点边容斥，扫描线维护。之后应该会写。

10.27 杂题

P6466 分散层叠算法(Fractional Cascading)

题意

给出 $k$ 个长为 $n$ 的有序数组，$q$ 次查询 $x$ 在每个数组中的非严格后继。强制在线，$k\le 100,n\le 10^4,q\le 5\times 10^5$。

题解

显然有 $\mathcal O(qk\log n)$ 的暴力，即对每个数组分别二分。尝试通过某种方式在第一次二分时处理部分后面的信息。先考虑两个序列的情况，将第二个序列偶数位置的元素插入第一个序列，这样在第一个序列中二分出结果后，第二个序列的答案只会在长为 $2$ 的区间内，可以 $\mathcal O(1)$ 求出。

拓展到 $k$ 个序列的情况，从后往前依次处理，每次将当前序列偶数位置的值插入上一个，使用归并排序即可。这样倒数第二个序列有 $1.5n$ 个元素，之后是 $1.75n,1.875n$ 等等，可以发现永远不会超过 $2n$。同时预处理出每个序列每个位置及之后第一个当前 / 之后序列元素，这样只需要在第一个序列中二分，后面全都可以 $\mathcal O(1)$ 微调出来，于是可以做到 $\mathcal O((n+q)k+q\log n)$ 的复杂度。

P11721 [清华集训 2014] 玄学

可离线时建线段树并在对应节点上分别二分，在线动态构建线段树可以 2log，再加上分散层叠可以 1log。之后应该会写。

10.28 做题？

问题

• 组合统计问题：计数 / 最优化 / 判定 / 构造。

关心组合结构：整体结构 / 个别判定。

组合研究工具：调整 / 差分生成 / 整体刻画观察。

• • 数据结构。
  • 交互。
  • 并行？流？强强？？！！？？

• （精确）（符号）计算问题。

• 数值计算问题。

研究方法

• 理论推导。
• 实验。

特例、特殊性质 / 画图、打表、渐进估计、验证。

可能性质 / 信息压缩、化简 / 刻画形式。

问题分类

• DP。
• DS。
• 子问题（分治、倍增）+ 微调。
• 优化 - 构造。
• 随机 - 近似。

UOJ792【UR #24】比特跳舞

讲“做题？”的例题，考虑刻画奇数个本质不同子序列的限制，发现可以从开头起每次跳到下一个相同位置，看是否能跳完即可。然后再注意一下或打表可以发现树上形成了若干个组，每个组内两两合法。于是用每对极小合法对合成大的组即可。之后应该会写。